package com.backpack;

/**
 * 输入：coins = [1, 2, 5], amount = 11
 * 输出：3
 * 解释：11 = 5 + 5 + 1
 * 凑成总金额的最少硬币个数，凑不成就返回-1；
 */
public class CoinChange0112_322 {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0) return 0;
        //元素都可重复，为完全背包问题，
        //dp[j] 表示 容量总价值为i的背包 至少有dp[j]个元素个数。 求dp[amount]，即总价值为amount的背包的元素个数
        int[] dp = new int[amount + 1];

        //初始化 ,非0下标初始化最大值，因为后面递推公式要取min
        dp[0] = 0;
        for (int i = 1; i < amount + 1; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        //递推公式：dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1);
        //遍历顺序：先遍历物品，再遍历背包容量（正序，因为背包中每种硬币无限多个），顺序可颠倒？
        for (int i = 0; i < coins.length; i++) {  //物品
            for (int j = coins[i]; j <= amount; j++) { //背包
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要!!!!!
                if(dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j],dp[j-coins[i]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
